//一个树状数组
class TreeArray{
    tree:number[]
    constructor(private n:number){
        this.tree = new Array(n+1).fill(0)
    }

    lowbit(x:number):number{
        return x&(-x)
    }

    query(x:number):number{
        let ans = 0
        while(x>0){
            ans += this.tree[x]
            x -= this.lowbit(x)
        }
        return ans
    }

    update(x:number,d:number){
         while(x<=this.n){
             this.tree[x]+=d
             x+=this.lowbit(x)
         }
    }
}
    

// 315. 计算右侧小于当前元素的个数
function countSmaller(nums: number[]): number[] {
    /**
     * 这几个都是离散化树状数组
     * 树状数组的作用就是边更新边计算前缀和
     * 离散化的作用就是把原来的值映射到一个连续的区间，且保证偏序关系不变，使得数组开得尽量小
     * 这个题也能用数字本身去建立树状数组，但是可能空间损耗太大
     */
    
    //使用数字的顺序做离散化
    let set = new Set([...nums].sort((a,b)=>a-b))
    let map = new Map<number,number>()
    let idx = 0
    //使用map加速映射关系的查找
    for(let n of set){
        map.set(n,++idx)
    }

    let tree = new TreeArray(map.size+1)
    let res:number[]= []
    //从后向前统计
    for(let i=nums.length-1;i>=0;i--){
        const t = nums[i]
        const index = map.get(t)!
        //这个时候i后面的元素都进去了，只需要统计序号小于index的个数就行
        res.push(tree.query(index-1))
        tree.update(index,1)
    }
    return res.reverse()
};

// 493. 翻转对
function reversePair(nums:number[]):number{
    const allNumbers = Array.from(
        new Set([...nums,...nums.map(x=>2*x)].sort((a,b)=>a-b))
    )

    const values = new Map<number,number>()

    let idx = 0
    allNumbers.forEach(x=>values.set(x,++idx))
    const tree = new TreeArray(values.size)
    let ret = 0
    // for(let n of nums){
    //     //转化了一下，没有直接求它大于右边数的2倍的个数
    //     //而是求左边大于它的2倍的数的个数
    //     let left = values.get(n*2)!
    //     let right = values.size
    //     ret+= tree.query(right) - tree.query(left)
    //     tree.update(values.get(n)!,1) 
    // }
    for(let n of nums.reverse()){
        ret += tree.query(values.get(n)!-1)
        tree.update(values.get(2*n)!,1)
    }
    return ret
}

// 327. 区间和的个数
function countRangeSum(nums: number[], lower: number, upper: number): number {
    let ans = 0
    //前缀和,第一个空着,方便相减求0-x的和
    //[i,j]的就是pre[j]-pre[i-1],那从0开始的过程就不统一了
    //0位置置为0求法就是pre[j+1]-pre[i]
    const pre = new Array<number>(nums.length+1)
    pre[0] = 0
    for(let i=1;i<=nums.length;i++){
        pre[i]=pre[i-1]+nums[i-1]
    }
    //离散化
    //因为要统计树状数组中的x-upper到x-lower的个数,就需要获取这两个值在
    //数组中的下标,因而需要把他们一起进行排序
    const set = new Set<number>([...pre,...pre.map(x=>x-lower),...pre.map(x=>x-upper)].sort((a,b)=>a-b))
    const map = new Map<number,number>()
    let idx = 1
    for(let it of set){
        map.set(it,idx++)
    }
    //开始边查边更新
    const tree = new TreeArray(map.size+1)
    for(let n of pre){
        const l = map.get(n-upper)!
        const r = map.get(n-lower)!
        ans += tree.query(r) - tree.query(l-1)
        tree.update(map.get(n)!,1)
    }
    return ans
};

console.log(
    countRangeSum([-1,1]
        ,0
        ,0)
    
)
